1. Field of the Invention
The present invention relates to cellular telecommunications and, more particularly, to methods and apparatus for assigning frequencies in a cellular network.
2. Description of the Related Art
Cellular telephone providers supply cellular telephone service to callers within cellular telephone networks. Each network covers a geographic area that is divided into several smaller regions, generally referred to as cells. When a caller within a cell makes a cellular telephone call, the caller's cellular telephone establishes a connection with transmission/reception hardware within that cell. This hardware is generally referred to as a base station. The connection requires a pair of frequencies, one frequency to carry a first signal from the base station to the caller's telephone, and another frequency to carry a second signal from the caller's telephone to the base station.
A provider is typically allocated a pool of frequencies for use within a network. The provider controls the assignment of the frequencies of the pool to various cells in the network. To handle the demand for cellular telephone connections in a typical network, the provider must often reuse frequencies, i.e., assign the same frequency to more than one cell in the network.
Reuse of frequencies within a network may cause problems. In particular, use of a particular frequency in one cell may increase radio interference at that frequency in other cells. In some circumstances, a frequency becomes unusable in a cell because the combined interference from use of that frequency in other cells is too great. Usually when a caller attempts to use a frequency having excessive interference, the caller's connection fails. If frequencies are reused in cells that are too close together, a signal from one caller's connection in one cell may be overheard by another caller in another cell.
The problem of assigning frequencies within a cellular network, such that frequencies are reused and the above-described interference problems are avoided, is commonly referred to as the frequency assignment problem, and has been studied extensively. However, it appears that only a few approaches to the frequency assignment problem have been implemented in real cellular networks.
One such approach is a manual approach. In particular, sets of frequencies are assigned manually to cells. This approach is commonly used in practice.
Another approach is more automated and involves treating the frequency assignment problem as a graph coloring problem. In this approach, a nodal map of the network is developed, with each cell of the network plotted as a node. Frequencies are grouped into sets, with each set assigned a particular color. Then, each node on the map is assigned a color such that the number of colors is minimized, and such that no two adjacent nodes have the same color.
Attempts at implementing the graph coloring algorithm have been well documented. In particular, an article entitled "On Frequency Assignment in Mobile Automatic Telephone Systems," by Andreas Gamst and Werner Rave, IEEE (1982) B3.1.1, pp. 309-315, discusses several variations of the graph coloring method. Further variations of the graph coloring method are provided in an article entitled "Channel Assignment in Cellular Radio," by Kumar Sivarajan and Robert McEliece, IEEE (1989) Ch. 2379, pp. 846-850.
There are several drawbacks to the graph coloring method. First, the graph coloring method does not adequately represent real world situations, because it attempts to minimize the number of frequencies used in the network. Since cellular providers are typically allocated pools of frequencies, the number of frequencies is fixed, and there is no need to minimize the number of frequencies. Second, minimizing the number of frequencies may result in some frequencies of the pool being under-utilized and other frequencies being over-utilized. Over-utilization of frequencies typically produces unnecessarily high amounts of interference. Third, the graph coloring method does not take into account varying amounts of interference between cells. For example, the graph coloring method treats the interference for 10 frequencies the same as the interference for 50 frequencies.
Another approach to the frequency assignment problem is called applied frequency planning. In the applied frequency planning method, each cell has a "rest-capacity" that is a function of the maximum number of frequencies that can be assigned to the cell. The lower rest-capacity cells receive assignments before the higher rest-capacity cells. The applied frequency planning method is described in an article entitled "Applied Frequency Assignment," by J. Plehn, IEEE (1994) 0-7803-1927, pp. 853-857.
There are several drawbacks to the applied frequency planning method. First, the applied frequency planning method gives priority to the lower rest-capacity cells, assuming that it is harder to assign frequencies to those cells than to the higher rest-capacity cells. However, the higher rest-capacity cells may also have higher constraints with other cells, thus making it more difficult to assign frequencies to the higher rest-capacity cells than the lower rest-capacity cells. Another drawback is that the applied frequency planning method considers carrier-to-interference ratios only when two cells have the same rest-capacity. Accordingly, a cell could be considered a high rest-capacity cell although most of the available frequencies have inadequate carrier-to-interference ratios. Furthermore, the applied frequency planning method requires a significant amount of time to compute the rest-capacity for each cell prior to each assignment.
It is therefore desirable to provide methods and apparatus for assigning frequencies in a cellular network that avoid the drawbacks of the conventional approaches. It is also desirable to provide methods and apparatus for improving the number of assignments, average carrier-to-interference ratios, carrier-to-interference variability and worst-case carrier-to-interference ratios in a cellular network.